import java.util.*;
import java.io.*;

public class PlayerSkeleton {
	public static BufferedWriter bw;
	public static final int COLS = 10;
	public static final int ROWS = 21;
	public static final int N_PIECES = 7;
	public static final int N_FEATURES = 10;

	private static int[][] pWidth = { { 2 }, { 1, 4 }, { 2, 3, 2, 3 },
			{ 2, 3, 2, 3 }, { 2, 3, 2, 3 }, { 3, 2 }, { 3, 2 } };
	private static int[][] pHeight = { { 2 }, { 4, 1 }, { 3, 2, 3, 2 },
			{ 3, 2, 3, 2 }, { 3, 2, 3, 2 }, { 2, 3 }, { 2, 3 } };
	private static int[][][] pBottom = { { { 0, 0 } },
			{ { 0 }, { 0, 0, 0, 0 } },
			{ { 0, 0 }, { 0, 1, 1 }, { 2, 0 }, { 0, 0, 0 } },
			{ { 0, 0 }, { 0, 0, 0 }, { 0, 2 }, { 1, 1, 0 } },
			{ { 0, 1 }, { 1, 0, 1 }, { 1, 0 }, { 0, 0, 0 } },
			{ { 0, 0, 1 }, { 1, 0 } }, { { 1, 0, 0 }, { 0, 1 } } };
	private static int[][][] pTop = { { { 2, 2 } }, { { 4 }, { 1, 1, 1, 1 } },
			{ { 3, 1 }, { 2, 2, 2 }, { 3, 3 }, { 1, 1, 2 } },
			{ { 1, 3 }, { 2, 1, 1 }, { 3, 3 }, { 2, 2, 2 } },
			{ { 3, 2 }, { 2, 2, 2 }, { 2, 3 }, { 1, 2, 1 } },
			{ { 1, 2, 2 }, { 3, 2 } }, { { 2, 2, 1 }, { 2, 3 } } };

	// Helper function: to get number of wells
	public int numOfWells(State s) {
		int[][] field = s.getField();
		int wells = 0;
		for (int i = 0; i < ROWS; i++) {
			for (int j = 1; j < COLS - 1; j++) {
				if (j != 0 && j != COLS - 1 && field[i][j] == 0
						&& field[i][j - 1] != 0 && field[i][j + 1] != 0) {
					wells++;
				}
			}
		}
		return wells;
	}

	// implement this function to have a working system
	// In this function,
	// We will call the our customised pickMove function with our best weights
	public int pickMove(State s, int[][] legalMoves) {
		Double[] weights = { -30.361175210619287, -38.6555747943614,
				51.76459565868514, -43.57806950701204, -194.47876313480097,
				-50.89214664871062, -69.18605211041972, -46.027834775907074,
				-18.72105970258877, -10.71129271087586 };
		return pickMove(s, legalMoves, weights);
	}

	// customised pickMove function
	// In this function,
	// We will find the best move using the weights given and heuristics function
	// This method is also used in Genetic Algorithm to customise the weights
	public int pickMove(State s, int[][] legalMoves, Double[] weights) {
		int nextPiece = s.getNextPiece();
		double currentBest = -1000000;
		int bestMove = 0;
		
		//							   XX
		// directly insert square tile XX and long tile  XXXX
		if ((nextPiece == 0 || nextPiece == 1) && numOfWells(s) > 0) {
			// only care about number of rows cleared (get max row cleared)
			Double[] specialweights = { 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
					0.0, 0.0 };

			for (int i = 0; i < legalMoves.length; i++) {
				double currentHeuristics = heuristics(s, nextPiece,
						legalMoves[i][0], legalMoves[i][1], specialweights);
				if (currentHeuristics > currentBest) {
					currentBest = currentHeuristics;
					bestMove = i;
				}
			}

			// now check how many rows cleared
			// if clear less than 2 rows then rather use the normal one
			if (currentBest < 2) { 
				// reset current best
				currentBest = -1000000;

				for (int i = 0; i < legalMoves.length; i++) {
					double currentHeuristics = heuristics(s, nextPiece,
							legalMoves[i][0], legalMoves[i][1], weights);
					if (currentHeuristics > currentBest) {
						currentBest = currentHeuristics;
						bestMove = i;
					}
				}
			}
		}
		// the normal one
		else {
			for (int i = 0; i < legalMoves.length; i++) {
				double currentHeuristics = heuristics(s, nextPiece,
						legalMoves[i][0], legalMoves[i][1], weights);
				if (currentHeuristics > currentBest) {
					currentBest = currentHeuristics;
					bestMove = i;
				}
			}
		}
		
		return bestMove;
	}

	// In this function,
	// We will returns the value of the heuristics function based on 
	// the current state and the next piece
	public double heuristics(State s, int piece, int orient, int slot,
			Double[] weights) {
		
		// Copy the field array from the state
		int[][] fieldTemp = s.getField();
		int[][] field = new int[ROWS][COLS];
		for (int i = 0; i < ROWS; i++) {
			for (int j = 0; j < COLS; j++) {
				field[i][j] = fieldTemp[i][j];
			}
		}
		
		// Copy the top array and turn number from the state. Top array contains
		// the height of each columns
		int[] top = Arrays.copyOf(s.getTop(), COLS);
		int turn = s.getTurnNumber() + 1;

		// Compute the tallest point reached by adding the new block
		int height = top[slot] - pBottom[piece][orient][0];
		for (int c = 1; c < pWidth[piece][orient]; c++) {
			height = Math
					.max(height, top[slot + c] - pBottom[piece][orient][c]);
		}

		// Return a really really small number when if the game will be lost
		if (height + pHeight[piece][orient] >= ROWS) {
			return -1000000;
		}

		// Mark the position of the new block
		for (int i = 0; i < pWidth[piece][orient]; i++) {
			for (int h = height + pBottom[piece][orient][i]; h < height
					+ pTop[piece][orient][i]; h++) {
				field[h][i + slot] = turn;
			}
		}

		// Feature 1: Newest height reached
		int newTopHeight = 0;
		// Adjust top
		for (int c = 0; c < pWidth[piece][orient]; c++) {
			top[slot + c] = height + pTop[piece][orient][c];
			newTopHeight = Math.max(newTopHeight, top[slot + c]);
		}

		// Feature 2: Number of rows cleared
		int rowsCleared = 0;
		// check for full rows - starting at the top
		for (int r = height + pHeight[piece][orient] - 1; r >= height; r--) {
			// check all columns in the row
			boolean full = true;
			for (int c = 0; c < COLS; c++) {
				if (field[r][c] == 0) {
					full = false;
					break;
				}
			}
			// if the row was full - remove it and slide above stuff down
			if (full) {
				rowsCleared++;
				// for each column
				for (int c = 0; c < COLS; c++) {
					// slide down all bricks
					for (int i = r; i < top[c]; i++) {
						field[i][c] = field[i + 1][c];
					}
					// lower the top
					top[c]--;
					while (top[c] >= 1 && field[top[c] - 1][c] == 0) {
						top[c]--;
					}
				}
			}
		}

		// Feature 3: Number of row transitions
		int rowTransitions = 0;
		for (int i = 0; i < ROWS; i++) {
			for (int j = 0; j < COLS - 1; j++) {
				if ((field[i][j] & field[i][j + 1]) == 0) {
					rowTransitions++;
				}
			}
		}

		// Feature 4: Number of column transitions
		int columnTransitions = 0;
		for (int i = 0; i < ROWS - 1; i++) {
			for (int j = 0; j < COLS; j++) {
				if ((field[i][j] & field[i + 1][j]) == 0) {
					columnTransitions++;
				}
			}
		}

		// Feature 5: Number of holes
		int holes = 0;
		for (int j = 0; j < COLS; j++) {
			boolean startCount = false;
			for (int i = ROWS - 1; i >= 0; i--) {
				if (!startCount && field[i][j] != 0) {
					startCount = true;
				} else if (startCount && field[i][j] == 0) {
					holes++;
				}
			}
		}

		// Feature 6: Number of wells
		int wells = 0;
		for (int i = 0; i < ROWS; i++) {
			for (int j = 1; j < COLS - 1; j++) {
				if (j != 0 && j != COLS - 1 && field[i][j] == 0
						&& field[i][j - 1] != 0 && field[i][j + 1] != 0) {
					wells++;
				}
			}
		}

		// Feature 7: Number of wells at the sides
		int sidewells = 0;
		for (int i = 0; i < ROWS; i++) {
			if (field[i][0] == 0 && field[i][1] != 0)
				sidewells++;
			if (field[i][COLS - 1] == 0 && field[i][COLS - 2] != 0)
				sidewells++;
		}

		// Feature 8: Difference in adjacent height
		int diffAdjacentHeight = 0;
		for (int i = 1; i < COLS; i++) {
			diffAdjacentHeight += Math.abs(top[i] - top[i - 1]);
		}

		// Feature 9: Maximum well depth
		int maxWellDepth = 0;
		int[] wellDepths = new int[COLS];
		for (int j = 0; j < COLS - 1; j++)
			for (int i = 0; i < ROWS; i++) {
				// If block is found above a space, it is no longer a well
				if (wellDepths[j] != 0 && field[i][j] != 0)
					wellDepths[j] = 0;
				else if (field[i][j] == 0 && field[i][j + 1] != 0) {
					wellDepths[j] += 1;
					int count = 1;
					while (i - count >= 0 && field[i - count][j] == 0
							&& field[i - count][j + 1] == 0) {
						// If shape is like:
						// |x| |x|x|x|... <- well discovered here (2nd Col)
						// |x| | |x|x|... <- add this to well depth (2nd Col)
						// |x|x|x|x|x|...
						// Add to well depth for areas where there are wells
						// beside
						// holes.
						wellDepths[j] += 1;
						count++;
					}
				}
			}
		for (int i = 0; i < COLS; i++) {
			if (wellDepths[i] > maxWellDepth)
				maxWellDepth = wellDepths[i];
			// Can also modify this to calculate total well depths or something.
		}

		// Feature 10: Blockages
		// *Note: anything found above a hole is a blockage
		int blockages = 0;
		for (int j = 0; j < COLS; j++) {
			boolean startCount = false;
			for (int i = 0; i < ROWS; i++) {
				if (!startCount && field[i][j] == 0) {
					startCount = true;
				} else if (startCount && field[i][j] != 0) {
					blockages++;
				}
			}
		}

		double[] features = new double[N_FEATURES];
		features[0] = newTopHeight;
		features[1] = rowsCleared;
		features[2] = rowTransitions;
		features[3] = columnTransitions;
		features[4] = holes;
		features[5] = wells;
		features[6] = sidewells;
		features[7] = diffAdjacentHeight;
		features[8] = maxWellDepth;
		features[9] = blockages;

		int result = 0;
		for (int i = 0; i < N_FEATURES; i++) {
			result += features[i] * weights[i];
		}
		return result;
	}

	/*
	// Particle Swarm Optimisation function
	public static void particleSwarmOptimisation() {

		// Pre-initialisation preparatory work...

		int N_PARTICLES = 50;
		int N_ITERATION = 1000;

		Particle[] swarm = new Particle[N_PARTICLES];
		Double[] bestGlobalPosition = new Double[N_FEATURES];
		double bestGlobalFitness = -1000000.0;

		// This is the range for the values in the weight
		double high = 5.0;
		double low = -5.0;
		double range = high - low;

		// Initialisation of particle swarm
		for (int i = 0; i < N_PARTICLES; i++) {
			// Create a random new position and velocity for the particle
			Double[] newPosition = new Double[N_FEATURES];

			// Make up the numbers
			for (int j = 0; j < N_FEATURES; j++) {
				newPosition[j] = Math.random() * (high - low) + low;
			}

			double fitness = fitness(newPosition);
			Double[] newVelocity = new Double[N_FEATURES];
			for (int j = 0; j < N_FEATURES; j++) {
				newVelocity[j] = Math.random() * (high - low) + low;
			}
			swarm[i] = new Particle(newPosition, fitness, newVelocity,
					newPosition, fitness);

			// Update the global best fitness and position
			if (fitness > bestGlobalFitness) {
				bestGlobalFitness = fitness;
				bestGlobalPosition = Arrays.copyOf(newPosition, N_FEATURES);
			}
		}

		// Particle Swarm Optimisation is about to start... buckle up!

		double w = 0.729;
		double c1 = 1.49445;
		double c2 = 1.49445;

		// Off we go!

		for (int iteration = 0; iteration < N_ITERATION; iteration++) {
			System.out.println("==========================\n" + "Iteration "
					+ iteration + "\n==========================\n");
			for (int i = 0; i < N_PARTICLES; i++) {

				Particle currentParticle = swarm[i];

				Double[] currentVelocity = currentParticle.getVelocity();
				Double[] currentPosition = currentParticle.getPosition();
				Double[] currentBestPosition = currentParticle
						.getBestPosition();
				Double[] newPosition = new Double[N_FEATURES];
				Double[] newVelocity = new Double[N_FEATURES];

				// We update the velocity of the particle based on the current
				// best position of the particle and the global best position
				for (int j = 0; j < N_FEATURES; j++) {
					newVelocity[j] = (w * currentVelocity[j])
							+ (c1 * Math.random() * (currentBestPosition[j] - currentPosition[j]))
							+ (c2 * Math.random() * (bestGlobalPosition[j] - currentPosition[j]));
				}
				currentParticle.setVelocity(newVelocity);

				// Now, we shift the particle based on the updated velocity
				for (int j = 0; j < N_FEATURES; j++) {
					newPosition[j] = currentPosition[j] + newVelocity[j];
				}
				currentParticle.setPosition(newPosition);
				// System.out.println(Arrays.toString(newPosition));

				// Finally, we check if this particle performs better than the
				// global optimal
				double newFitness = fitness(newPosition);
				if (newFitness > currentParticle.getBestFitness()) {
					currentParticle.setBestPosition(newPosition);
					currentParticle.setBestFitness(newFitness);
				}
				if (newFitness > bestGlobalFitness) {
					bestGlobalFitness = newFitness;
					bestGlobalPosition = Arrays.copyOf(newPosition,
							newPosition.length);
					System.out.println("New best particle found at iteration "
							+ iteration + "!");
					System.out.println(currentParticle);
				}
			}
			System.out.println();
		}
	}

	// Genetic Algorithm function
	// Takes in two parents and produce the offspring after many generations
	public static Double[] geneticAlgorithm(Double[] adam, Double[] eve)
			throws IOException {
		int generations = 30;
		int populationSize = 16;

		boolean fineTuneMutation = false;

		// Stores the chromosomes of the offsprings
		ArrayList<Double[]> population = new ArrayList<Double[]>(populationSize);

		Double[] mother = adam;
		Double[] father = eve;

		for (int i = 0; i < generations; i++) {
			if (bw == null)
				System.out.printf("Starting %d-th generation, ", i + 1);
			else
				bw.write(String.format("Starting %d-th generation, ", i + 1));
			population.clear();

			population.add(mother);
			population.add(father);

			// Let the parents breed new offsprings
			for (int j = 0; j < populationSize - 2; j++) {
				Double[] newChromosome = new Double[N_FEATURES];
				for (int k = 0; k < N_FEATURES; k++) {
					// Same chance to obtain a chromosome from either parents
					if (Math.random() > 0.5) {
						newChromosome[k] = mother[k];
					} else {
						newChromosome[k] = father[k];
					}
					// if(Math.random() < 0.1) newChromosome[k] = Math.random()
					// * 10 - 5;
					newChromosome[k] = mutation(fineTuneMutation,
							newChromosome[k]);
				}
				population.add(newChromosome);
			}

			int[] results = new int[populationSize];
			double best = 0, secondbest = 0;
			int bestpos = 0, secondbestpos = 0;

			// Figure out the best offsprings and kill the other offsprings
			for (int j = 0; j < populationSize; j++) {
				results[j] = fitness(population.get(j));
				if (results[j] > best) {
					best = results[j];
					bestpos = j;
				} else if (results[j] > secondbest) {
					secondbest = results[j];
					secondbestpos = j;
				}
			}

			// Replace mom and dad
			mother = population.get(bestpos);
			father = population.get(secondbestpos);

			if (bw == null)
				System.out.println("Current best result = " + best
						+ ", Current best chromosome = "
						+ Arrays.toString(mother));
			else {
				bw.write("Current best result = " + best
						+ ", Current best chromosome = "
						+ Arrays.toString(mother));
				bw.newLine();
			}

		}
		// Mom is the best
		return mother;
	}

	// Mutation function
	public static double mutation(boolean fineTuning, double chromosomeVal) {
		double mutation = 0.1;
		Random r = new Random();

		if (!fineTuning) {
			// Leave some chance for mutation
			if (Math.random() < mutation) {
				return Math.random() * 10 - 5;
				// the following is natural mutation using normal distribution
			} else {
				double value = r.nextGaussian();
				// this makes it a SD of 0.1
				value = value / 10.0;
				return chromosomeVal + value;
			}
		} else {
			double value = r.nextGaussian();
			// this makes it a SD of 0.01
			value = value / 100.0;
			return chromosomeVal + value;
		}
	}

	// Method to decide how fit an offspring is
	public static int fitness(Double[] weights) {
		int result = 0;
		FitnessThread[] threads = new FitnessThread[10];
		for (int i = 0; i < 10; i++) {
			threads[i] = new FitnessThread(weights);
			threads[i].start();
		}
		try {
			for (int i = 0; i < 10; i++) {
				threads[i].join();
			}
			for (int i = 0; i < 10; i++) {
				result += threads[i].fitness;
			}
		} catch (InterruptedException IntExp) {
			System.out.println("Hope you won't reach here!");
		}
		return result / 10;
	}

	public static class FitnessThread extends Thread {
		public int fitness;
		Double[] weights;

		public FitnessThread(Double[] weights) {
			fitness = 0;
			this.weights = Arrays.copyOf(weights, weights.length);
		}

		public void run() {
			fitness = runOneGameUsingWeights(weights);
			// System.out.println("You have completed " + fitness + " row(s)!");
		}
	}

	public static int runOneGameUsingWeights(Double[] weights) {
		State s = new State();
		PlayerSkeleton p = new PlayerSkeleton();
		while (!s.hasLost()) {
			s.makeMove(p.pickMove(s, s.legalMoves(), weights));
		}
		return s.getRowsCleared();
	}

	public static void runGenericAlgorithmWithFileOutput() throws IOException {
		int k = 0;
		while (true) {
			String fileName = "File" + k + "txt";
			k++;
			File file = new File(fileName);
			if (!file.exists()) {
				file.createNewFile();
			}
			FileWriter fw = new FileWriter(file.getAbsoluteFile());
			bw = new BufferedWriter(fw);

			Double[] adam = { -2.008753906342281, 1.7580443502216812,
					-0.4310186078582551, 0.20604428526628038,
					-4.99962652178066, -1.625798166098838, -1.968429940059275,
					-4.0 };
			Double[] eve = new Double[N_FEATURES];
			for (int i = 0; i < N_FEATURES; i++) {
				eve[i] = Math.random() * 10 - 5;
			}
			geneticAlgorithm(adam, eve);

			bw.close();
		}
	}

	// Calculate the average and standard deviation after many trials
	public static void experiment() {
		int numTrials = 100;
		int totalCleared = 0;
		int minCleared = 10000000;
		int maxCleared = 0;
		int[] results = new int[numTrials];
		FitnessThread[] experimentThreads = new FitnessThread[numTrials];
		Double[] weights = {  -30.361175210619287, -38.6555747943614,
				51.76459565868514, -43.57806950701204, -194.47876313480097,
				-50.89214664871062, -69.18605211041972, -46.027834775907074,
				-18.72105970258877, -10.71129271087586  };

		try {
			for (int i = 0; i < numTrials; i++) {
				System.out.println("Starting Thread " + i);
				experimentThreads[i] = new FitnessThread(weights);
				experimentThreads[i].start();

			}
			for (int i = 0; i < numTrials; i++) {
				experimentThreads[i].join();
			}
			for (int i = 0; i < numTrials; i++) {
				results[i] += experimentThreads[i].fitness;
				totalCleared += results[i];
				maxCleared = Math.max(results[i], maxCleared);
				minCleared = Math.min(results[i], minCleared);
			}
		} catch (InterruptedException IntExp) {
			System.out.println("You should not reach here");
		}

		System.out.println("Maximum number of rows cleared: " + maxCleared
				+ " rows.");
		System.out.println("Minimum number of rows cleared: " + minCleared
				+ " rows.");

		double mean = ((double) totalCleared) / numTrials;
		System.out.println("Average number of rows cleared: " + mean
				+ " row(s).");
		double variance = 0;
		for (int i = 0; i < numTrials; i++) {
			variance += (((double) results[i]) - mean)
					* (((double) results[i]) - mean);
		}
		variance /= numTrials;
		double stdDev = Math.sqrt(variance);
		System.out.println("Standard deviation: " + stdDev);
	}
	*/
	
	// This is the original main function given
	public static void originalMain() {
		State s = new State();
		new TFrame(s);
		PlayerSkeleton p = new PlayerSkeleton();
		while (!s.hasLost()) {
			s.makeMove(p.pickMove(s, s.legalMoves()));
			s.draw();
			s.drawNext(0, 0);
			try {
				Thread.sleep(500);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		System.out.println("You have completed " + s.getRowsCleared()
				+ " rows.");
	}
	
	public static void main(String[] args) throws IOException {

		// experiment();
		originalMain();
		// particleSwarmOptimisation();

		// Double[] adam = new Double[N_FEATURES];
		// for (int i = 0; i < N_FEATURES; i++) {
		// adam[i] = Math.random() * 10 - 5;
		// }
		// Double[] eve = new Double[N_FEATURES];
		// for (int i = 0; i < N_FEATURES; i++) {
		// eve[i] = Math.random() * 10 - 5;
		// }
		//
		// geneticAlgorithm(adam, eve);

		// runGenericAlgorithmWithFileOutput();
	}

}
